#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

char* generate_random_string(int length) {
    char letters[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()-=_+[]{}|;':,.<>?";
    char *result = (char*)malloc((length + 1) * sizeof(char));
    srand(time(0));
    for (int i = 0; i < length; i++) {
        result[i] = letters[rand() % (sizeof(letters) - 1)];
    }
    result[length] = '\0';
    return result;
}

void expand_around_center(char *s, int left, int right, int* start, int* max_len) {
    int len = strlen(s);
    while (left >= 0 && right < len && s[left] == s[right]) {
        left--;
        right++;
    }
    if (right - left - 1 > *max_len) {
        *max_len = right - left - 1;
        *start = left + 1;
    }
}

void longest_palindrome2(char *s, char *result) {
    int len = strlen(s);
    int start = 0, max_len = 0;
    
    for (int i = 0; i < len; ++i) {
        expand_around_center(s, i, i, &start, &max_len);
        expand_around_center(s, i, i + 1, &start, &max_len);
    }
    
    strncpy(result, s + start, max_len);
    result[max_len] = '\0';
}

int main() {
    int length = 10000000;
    char* random_string = generate_random_string(length);

    clock_t start, end;
    double cpu_time_used;

    start = clock();

    char longest_palindrome[1000];
    longest_palindrome2(random_string, longest_palindrome);

    end = clock();

    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

    printf("Longest palindrome: %s\n", longest_palindrome);
    printf("Time taken: %f seconds\n", cpu_time_used);

    free(random_string);

    // printf("Press Enter to exit...\n");
    // getchar();
    // return 0;
}